package com.test.daily.leetcode.y2021.m12.day1225;

import java.util.*;

/**
 * IsEvenOddTree
 *
 * @author Tom on 2021/12/25
 */
public class Code01_IsEvenOddTree {
    public boolean isEvenOddTree(TreeNode root) {
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
            int level = 0;
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                int pre = level % 2 == 0 ? Integer.MIN_VALUE: Integer.MAX_VALUE;
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    int value = node.val;
                    if(level % 2 == value % 2 ){
                        return false;
                    }
                    if((level %2 == 0 && value<= pre)||(level % 2 ==1 && value >= pre)){
                        return false;
                    }
                    pre = value;
                    if(node.left != null){
                        queue.offer(node.left);
                    }
                    if(node.right != null){
                        queue.offer(node.right);
                    }
                }
                level++;

            }
            return true;
        }

      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
      }
  }
}
